package 数据结构.排序.实例;
/**
 * 希尔排序首先就是需要使用数组的长度进行确定增长量的初始值
 *      时间复杂度
 *      对希尔排序的时间复杂度分析很困难，在特定情况下可以准确的估算排序码的比较次数和元素移动的
 * 次数，但要想弄清楚排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到，有几种接近的答案：O(nlog2为底n)或O(n^1.25)。
 *
 *      空间复杂度
 *      由希尔排序算法可知，我们在排序过程中，需要一个增量元素，所以空间复杂度为 1 。
 *
 *      算法稳定性
 *      希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，
 * 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的
 * 相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
 * */

public class $05_希尔排序 {

    public static void min(int []a){
        int h=1;
        while(h<a.length/2){
            h*=2;h++;
        }
        while (h>=1){
            //找到带插入的元素
            for(int i=h;i<a.length;i++) { //把待插入的元素插入到有序数列中
                for (int j = i; j >= h; j -= h) {
                   //待插入元素是a[j],比较a[j]和a[j-h]
                    if(a[j-h]>a[j])
                        jiaohuan(a,j-h,j);
                    else
                        break;
                }
            }
            h/=2;
        }
        /*for(int i=1;i<a.length;i++){
            for(int j=i;j>0;j--){
                if(a[j-1]>a[j])
                    jiaohuan(a,j-1,j);
            }

        }*/
    }

    private static void jiaohuan(int []a,int i,int j){
        int num=a[i];
        a[i]=a[j];
        a[j]=num;
    }

}
